package com.cty.B_SpecialDataStructures.C_PriorityQ.PriorityQChain;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/14 20:48
 * @Description: 有序链表
 * 重要操作：
 *      ① insert(DataItem): void    O(N)
 *      ② deleteFirst(): DataItem    O(1)
 * @version: 1.0
 */
public class OrdLinkedList {
    private Node first;

    public OrdLinkedList(){
        first = null;
    }

    public boolean isEmpty(){
        return (first == null);
    }

    public void displayList(){
        Node current = first;
        while(current != null){
            System.out.print(current.data.getKey() + " ");
            current = current.next;
        }
        System.out.println();
    }

    /**
     * 降序插入  O(N)
     * @param item
     */
    public void insert(DataItem item){
        Node newNode = new Node(item);
        Node current = first;
        Node previous = null;

        // 找到第一个小于等于item关键字的节点
        while(current != null && item.getKey()<current.data.getKey()){
            previous = current;
            current = current.next;
        }

        // 在该节点前面插入
        newNode.next = current;
        if(previous == null)   // 在表头（包括空表和非空表情况）
            first = newNode;
        else  // 非表头（包括表身和表尾情况）
            previous.next = newNode;
    }  // end insert()

    /**
     * 移除表头  O(1)
     * @return
     */
    public DataItem deleteFirst(){
        if(isEmpty())
            return null;

        DataItem temp = first.data;
        first = first.next;
        return temp;
    }  // end remove()

}  // end OrdLinkedList{}
